#include <iostream>
#include <vector>

using namespace std;
int n1 = 0, n2 = 0;
const int N = 3e3 + 20;

// 邻接矩阵存储图
int adjacencyMatrix[N][N] = { {0} };
// visited 数组记录每个节点是否已经被访问过
bool visited_A[N] = { 0 };

void dfsA(int u, int* out, int n) {
    out[n1] = u;
    n1++;
    visited_A[u] = true;
    for (int v = 0; v < n; v++) {
        if (adjacencyMatrix[u][v] && !visited_A[v]) {
            dfsA(v, out, n);
        }
    }
}

void solveA(int n, int m, int e[][2], int out[]) {
    // 初始化图
    for (int i = 0; i < m; i++) {
        adjacencyMatrix[e[i][0]][e[i][1]] = 1;
        adjacencyMatrix[e[i][1]][e[i][0]] = 1;
    }

    // 从节点 0 开始进行深度优先遍历
    dfsA(0, out, n);
}
//
// 
// 
// 
// 
// 
// 

// 邻接链表存储图
std::vector<std::vector<int>> adjacencyList(N);
// visited 数组记录每个节点是否已经被访问过
bool visited_B[N] = { 0 };

void dfs_B(int u, int* out) {
    out[n2] = u;
    n2++;
    visited_B[u] = true;
    for (std::vector<int>::iterator it = adjacencyList[u].begin(); it != adjacencyList[u].end(); ++it) {
        int v = *it;
        if (!visited_B[v]) {
            dfs_B(v, out);
        }

    }
}

void solveB(int n, int m, int e[][2], int out[]) {
    // 初始化图
    for (int i = 0; i < m; i++) {
        adjacencyList[e[i][0]].push_back(e[i][1]);
        adjacencyList[e[i][1]].push_back(e[i][0]);
    }

    // 从节点 0 开始进行深度优先遍历
    dfs_B(0, out);
}